P3241 [HNOI2015]开店

发表于

闲扯

动态点分治的常数是真的大。。。

题面

P3241 [HNOI2015]开店

Solution

这道题有两种思路：

树链剖分+动态开店点线段树

先写出答案要求的式子：

其中，我们设 $dis_u$ 表示 $u$ 到根结点的距离， $sum_dis=\sum_{i=1}^ndis_i$ 。

然后我们只需要解决 $\sum dis_{lca_{u,i}}$ 即可。

然而这是一个经典问题，直接用树剖维护即可。

由于题目要求 $[L,R]$ 之间的答案，所以我们用主席树求解即可。（不过貌似有点卡空间，需要用到标记永久化，不过不太会，就没写）

动态点分治

动态点分治经典题目。

先建出点分树，然后考虑怎么维护。

套路性的，我们维护 $dis1_u,dis2_u,sum_u$ 分别表示点 $u$ 的子树中的点到 $u$ 的距离，到 $fa_u$ 的距离，以及点的个数。

根据点分树的性质，我们可以得到空间占用为 $n\log n$ 级别。

如果不考虑 $[L,R]$ 的限制，我们直接计算即可（方法与换根 $DP$ 类似）。

但是现在有了 $L,R$ 的限制，考虑怎么做。

我们可以将上面的三组变量存在 $vector$ 里面，同时用 $pair$ 记录下对应的颜色。

然后我们将它们按照颜色从小到大排序，然后求一个前缀和。

在在询问时，我们二分出有用的区间即可。

点分树暴力跳 $fa$ 复杂度为 $O(n\log n)$ ，每个点查询贡献复杂度为 $O(\log n)$ ，总复杂度为 $O(n\log^2 n)$ 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 15e4+5;
int n,m,A,u,v,d,val[MAXN],x,y,head[MAXN],num_edge;
ll lst;
char vis[MAXN];
struct Edge{
	int next,to;
	Edge(){}
	Edge(int next,int to):next(next),to(to){}
}edge[MAXN<<1];
il add_edge(int u,int v){
	edge[++num_edge]=Edge(head[u],v),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u),head[v]=num_edge;
}
struct Graph{
	int head[MAXN],num_edge,dis[MAXN];
	struct Edge{
		int next,to,dis;
		Edge(){}
		Edge(int next,int to,int dis):next(next),to(to),dis(dis){}
	}edge[MAXN<<1];
	il add_edge(int u,int v,int dis){
		edge[++num_edge]=Edge(head[u],v,dis),head[u]=num_edge;
		edge[++num_edge]=Edge(head[v],u,dis),head[v]=num_edge;
	}
	int f[MAXN],sz[MAXN],son[MAXN],dep[MAXN],top[MAXN];
	il DFS1(int u,int fa){
		f[u]=fa,sz[u]=1,dep[u]=dep[fa]+1;
		for(ri i=head[u];i;i=edge[i].next){
			if(edge[i].to==fa) continue;
			dis[edge[i].to]=dis[u]+edge[i].dis,DFS1(edge[i].to,u),sz[u]+=sz[edge[i].to];
			if(sz[edge[i].to]>sz[son[u]]) son[u]=edge[i].to;
		}
	}
	il DFS2(int u,int t){
		top[u]=t;
		if(!son[u]) return ;
		DFS2(son[u],t);
		for(ri i=head[u];i;i=edge[i].next){
			if(edge[i].to==f[u]||edge[i].to==son[u]) continue;
			DFS2(edge[i].to,edge[i].to);
		}
	}
	it LCA(int u,int v){
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]]) swap(u,v);
			u=f[top[u]];
		}
		return dep[u]<dep[v]?u:v;
	}
	it Query(int u,int v){return dis[u]+dis[v]-2*dis[LCA(u,v)];}
	il Init(){
		for(ri i=1;i<n;++i)
			read(u),read(v),read(d),add_edge(u,v,d);
		DFS1(1,0),DFS2(1,1);
	}
}G;
int S,mx,rt,sz[MAXN],fa[MAXN];
il Get_Rt(int u,int fa){
	sz[u]=1;int mx1=0;
	for(ri i=G.head[u];i;i=G.edge[i].next){
		if(G.edge[i].to==fa||vis[G.edge[i].to])
			continue;
		Get_Rt(G.edge[i].to,u),sz[u]+=sz[G.edge[i].to];
		mx1=max(mx1,sz[G.edge[i].to]);
	}
	mx1=max(mx1,S-sz[u]);
	if(mx1<mx)
		mx=mx1,rt=u;
}
il Solve(int u){
	vis[u]=1;
	for(ri i=G.head[u];i;i=G.edge[i].next){
		if(vis[G.edge[i].to])
			continue;
		S=sz[G.edge[i].to],mx=INF,Get_Rt(G.edge[i].to,u);
		fa[rt]=u,add_edge(u,rt),Solve(rt);
	}
}
vector<pair<int,ll> > dis1[MAXN],dis2[MAXN],sum[MAXN];
il Updata(int u,int ty){
	sum[u].push_back(make_pair(ty,1));
	for(ri i=u;fa[i];i=fa[i]){
		int dist=G.Query(u,fa[i]);
		dis1[fa[i]].push_back(make_pair(ty,dist));
		dis2[i].push_back(make_pair(ty,dist));
		sum[fa[i]].push_back(make_pair(ty,1));
	}
}
inl bool cmp(pair<int,ll> &x,pair<int,ll> &y){
	return x.first<y.first;
}
vector<pair<int,ll> > Dis1[MAXN],Dis2[MAXN],Sz[MAXN];
il Init(){
	for(ri i=1;i<=n;++i){
		sort(dis1[i].begin(),dis1[i].end(),cmp);
		sort(dis2[i].begin(),dis2[i].end(),cmp);
		sort(sum[i].begin(),sum[i].end(),cmp);
		int j=0;
		for(j=0;j<(int)dis1[i].size()-1;++j){
			dis1[i][j+1].second+=dis1[i][j].second;
			if(dis1[i][j].first!=dis1[i][j+1].first)
				Dis1[i].push_back(dis1[i][j]);
		}
		if(dis1[i].size()) Dis1[i].push_back(dis1[i][j]);
		for(j=0;j<(int)dis2[i].size()-1;++j){
			dis2[i][j+1].second+=dis2[i][j].second;
			if(dis2[i][j].first!=dis2[i][j+1].first)
				Dis2[i].push_back(dis2[i][j]);
		}
		if(dis2[i].size()) Dis2[i].push_back(dis2[i][(int)dis2[i].size()-1]);
		for(ri j=0;j<(int)sum[i].size()-1;++j){
			sum[i][j+1].second+=sum[i][j].second;
			if(sum[i][j].first!=sum[i][j+1].first)
				Sz[i].push_back(sum[i][j]);
		}
		if(sum[i].size()) Sz[i].push_back(sum[i][(int)sum[i].size()-1]);
	}
}
ill Calc(int u,int L,int R,vector<pair<int,ll> > &vec){
	if(!vec.size())	return 0;
	ll res=0;
	int l=0,r=vec.size()-1;
	if(vec[r].first<L||vec[l].first>R)
		return 0;
	while(l<r){
		if(vec[mid+1].first<=R) l=mid+1;
		else r=mid;
	}
	res+=vec[l].second;
	l=0,r=vec.size()-1;
	while(l<r){
		if(vec[mid].first>=L) r=mid;
		else l=mid+1;
	}
	res-=l==0?0:vec[l-1].second;
	return res;
}
ill Get_Sz(int u,int L,int R){
	if(!Sz[u].size()) return 0;
	ll res=0;
	int l=0,r=Sz[u].size()-1;
	if(Sz[u][r].first<L||Sz[u][l].first>R)
		return 0;
	while(l<r){
		if(Sz[u][mid+1].first<=R) l=mid+1;
		else r=mid;
	}
	res+=Sz[u][l].second;
	l=0,r=Sz[u].size()-1;
	while(l<r){
		if(Sz[u][mid].first>=L) r=mid;
		else l=mid+1;
	}
	res-=l==0?0:Sz[u][l-1].second;
	return res;
}
ill Query(int u,int L,int R){
	ll res=Calc(u,L,R,Dis1[u]);
	for(ri i=u;fa[i];i=fa[i]){
		int dist=G.Query(u,fa[i]);
		res+=Calc(fa[i],L,R,Dis1[fa[i]])-Calc(i,L,R,Dis2[i]);
		res+=dist*(Get_Sz(fa[i],L,R)-Get_Sz(i,L,R));
	}
	return res;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),read(A);
	for(ri i=1;i<=n;++i)
		read(val[i]);
	G.Init();
	S=n,mx=INF,Get_Rt(1,0),Solve(rt);
	for(ri i=1;i<=n;++i)
		Updata(i,val[i]);
	Init();
	for(ri i=1;i<=m;++i){
		read(u),read(x),read(y);
		x=(x+lst)%A,y=(y+lst)%A;
		if(x>y) swap(x,y);
		print(lst=Query(u,x,y)),puts("");
	}
	return 0;
}